package leetcode;


public class LeetCode69 {


    public int mySqrt1(int x) {
        return (int) Math.sqrt(x);
    }

    //数学办法 换底
    public int mySqrt2(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }

    //二分法
    public int mySqrt3(int x) {
        int left = 0, right = x, mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid * mid == x)
                return mid;
            else if (mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (long) (mid + 1) * (mid + 1) <= x ? mid + 1 : mid;
    }

    //找到k*k最接近x的k
    public int mySqrt4(int x) {
        int left = 0, right = x, mid = 0, result = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid * mid == x)
                return mid;
            else if (mid * mid < x) {
                left = mid + 1;
                result = mid;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
//------------------------------------------------------------------
}
